package com.example.question.dp.dp2;

import java.util.Arrays;

/**
 * @Date 2023-07-21
 * @Author Jonathan
 */
public class Code04_198 {
    public static void main(String[] args) {
        Code04_198 code = new Code04_198();
        int i = code.rob1(new int[]{1, 2, 3, 1});
    }

    public int rob(int[] nums) {
        int len = nums.length;
        // 一个元素的时候下面得递归处理不了
        if (len == 1) {
            return nums[0];
        }
        int[] dp = new int[len];
        Arrays.fill(dp, -1);
        return dfs(nums, 0, dp);
    }

    /**
     * 完全的暴力递归
     */
    private int dfs(int[] nums, int startIndex) {
        if (startIndex >= nums.length) {
            return 0;
        }
        if (startIndex == nums.length - 1) {
            return nums[startIndex];
        }
        int num1 = dfs(nums, startIndex + 1);
        int num2 = dfs(nums, startIndex + 2);
        // 当前节点不偷的话 就去偷下一个
        // 当前偷的话 就再偷下下个
        return Math.max(num1, nums[startIndex] + num2);
    }

    /**
     * 记忆化搜索
     *
     * @param nums
     * @param startIndex
     * @param dp
     * @return
     */
    private int dfs(int[] nums, int startIndex, int[] dp) {
        if (startIndex >= nums.length) {
            return 0;
        }
        if (startIndex == nums.length - 1) {
            return nums[startIndex];
        }
        if (dp[startIndex] != -1) {
            return dp[startIndex];
        }
        int num1 = dfs(nums, startIndex + 1, dp);
        int num2 = dfs(nums, startIndex + 2, dp);
        // 当前节点不偷的话 就去偷下一个
        // 当前偷的话 就再偷下下个
        int max = Math.max(num1, nums[startIndex] + num2);
        return dp[startIndex] = max;
    }

    /**
     * 动态规划解法
     */
    private int rob1(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len + 1];
        dp[len - 1] = nums[len - 1];
        dp[len] = 0;
        for (int i = len - 2; i >= 0; i--) {
            dp[i] = Math.max(dp[i + 2] + nums[i], dp[i + 1]);
        }
        return dp[0];
    }
}
